package com.openess.bigsearch.engine.utils.sort;

import java.lang.reflect.Array;
import java.util.Comparator;

/**
 * 合并排序
 * 
 * @author TuTu
 * 
 */
public class MergeSort<E> implements Sort<E> {
	/**
	 * 合并两个已排好序的子数组，A[p, q]和A[q+1, r]
	 * 
	 * @param array
	 * @param p
	 *            起始位置
	 * @param q
	 *            子数组的分割位置，一般取(p+r)/2
	 * @param r
	 *            终止位置，包括r
	 */
	@SuppressWarnings("unchecked")
	private void merge(E[] array, int p, int q, int r, Comparator<? super E> c) {
		// 利用反射创建两个泛型数组
		E[] list1 = (E[]) Array.newInstance(
				array.getClass().getComponentType(), q - p + 1);
		E[] list2 = (E[]) Array.newInstance(
				array.getClass().getComponentType(), r - q);
		// 将两个子数组分别赋值
		System.arraycopy(array, p, list1, 0, q - p + 1);
		System.arraycopy(array, q + 1, list2, 0, r - q);
		// 合并两个子数组
		int i = 0;
		int j = 0;
		for (int n = p; n <= r; n++) {
			if (i >= list1.length) {
				array[n] = list2[j++];
			} else if (j >= list2.length) {
				array[n] = list1[i++];
			}
			if (i < list1.length && j < list2.length) {
				if (c.compare(list1[i], list2[j]) <= 0) {
					array[n] = list1[i++];
				} else {
					array[n] = list2[j++];
				}
			}
		}
	}

	/**
	 * 递归调用进行排序
	 * 
	 * @param array
	 * @param p
	 *            起始位置
	 * @param r
	 *            终止位置，包括r
	 */
	public void sort(E[] array, int p, int r, Comparator<? super E> c) {
		// 用于结束递归
		if (p >= r) {
			return;
		}
		int q = (p + r) / 2;
		sort(array, p, q, c);
		sort(array, q + 1, r, c);
		merge(array, p, q, r, c);
	}
}
